백준 9663번 - N-Queen

문제링크

풀이과정

기본적으로 한줄에 하나씩 퀸이 들어갈 수 있다.
즉, 15!이 가능하다 근데 이것은 너무 크므로 시간복잡도를 벗어난다.

그렇지만 퀸은 대각선으로도 움직일 수 있으므로 이보다 15,14,13,... 보다 감속폭이 크다고 할 수 있다.

사실 전에 풀어본 적이 있어서 어느 정도 알고 있었다.

이 문제의 핵심은 퀸들의 위치를 1차원 배열로 나타낼 수 있다는 것이다.

코드

n = int(input())
array = [0] * (n + 1)
count = 0
def backtrack(x, y):
    if y == n:
        global count
        count += 1
        return
    array[x] = y

    for idx, j in enumerate(array):
        if j != 0 or idx == 0:
            continue
        isPossi = True
        for a, b in enumerate(array):
            if b == 0:
                continue
            if abs((b - y - 1) / (a - idx)) == 1:
                isPossi = False
        if isPossi:
            backtrack(idx, y + 1)
    array[x] = 0


for i in range(1, n + 1):
    backtrack(i, 1)

print(count)